package day03;

/**
 * 10. 正则表达式匹配
 * https://leetcode.cn/problems/regular-expression-matching/description/
 */
public class No10 {
    // todo 不行,要重写
    public boolean isMatch(String s, String p) {
        if (".*".equals(p)) return true;
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        int i = 0, j = 0;
        while (i < cs.length && j < cp.length){
            if(".*".equals(p.substring(j))) return true;
            int end = searchPointStar(cp, j);
            if(end == -1){
                i =  backStrictComparison(s.substring( i), p.substring( j));
                if(i == -1) return false;
                if(j == 0 && i != 0) return false;
                return true;
            } else if (end == j) {
                j += 2;
            } else{
                if(j == 0){
                    int re = forwardComparison(s, p.substring(j,  end));
                    if(re == -1) return false;
                    i = i + re + end - j;
                    j = end+2;
                }else {
                    int re = forwardSearch(s.substring(i), p.substring(j, end));
                    if(re == -1) return false;
                    i = i + re + end - j;
                    j = end+2;
                }
            }
        }
        return i == cs.length && j == cp.length;
    }

    /**
     * 正向搜寻, 从s中寻找p, 返回匹配到的位置
     * @param s
     * @param p
     * @return
     */
    public int forwardSearch(String s, String p) {

        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        int i = 0;
        while(i < cs.length){
            if(cs[i] == cp[0] || cp[0] == '.'){
                int re = forwardComparison(s.substring(i), p);
                if(re != -1) return i+re;
                else i++;
            }else {
                i++;
            }
        }
        return -1;
    }

    /**
     * 正向比对,从头开始匹配p
     * @param s
     * @param p
     * @return
     */
    public int forwardComparison(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        int i = 0, j = 0;
        while(i < cs.length && j < cp.length){
            if(nextIsStar(cp, j)){
                while(i < cs.length && cs[i] == cp[j]){
                    i++;
                }
                j += 2;
            }else if(cp[j] == '.' || cs[i] == cp[j]){
                i++;
                j++;
            }else return -1;
        }
        return (j==cp.length ? i: -1);
    }

    /**
     * 逆向匹配
     * @param s
     * @param p
     * @return
     */
    public int backStrictComparison(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        int i = cs.length-1, j = cp.length-1;
        while(i >= 0 && j >= 0){
            if(cs[ i] == cp[j] || cp[j] == '.'){
                i--;
                j--;
            } else if (cp[j] == '*') {
                j -= 2;
                while(i >= 0 && cs[i] == cp[j+1]){
                    i--;
                }
            }else return -1;
        }
        if(i < 0 && j >= 0 && cp[j] == '*'){
            while(j >= 0 && cp[j] == '*'){
                j -= 2;
            }
        }
        return (j==-1 ? i+1 : -1);
    }

    public boolean nextIsStar(char[] cp, int j){
        return j+1 < cp.length && cp[j+1] == '*';
    }

    /**
     *  搜索下一个 .*
     * @param cp
     * @param j
     * @return
     */
    public int searchPointStar(char[] cp, int j){
        // 找到下一个 .*，返回下标，如果没有则返回-1
        while (j+1 < cp.length){
            if(cp[j] == '.' && cp[j+1] == '*'){
                return j;
            }else j++;
        }
        return -1;
    }
}
